0 CpxTRS
↳1 TrsToWeightedTrsProof (BOTH BOUNDS(ID, ID), 0 ms)
↳2 CpxWeightedTrs
↳3 CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID), 0 ms)
↳4 CpxWeightedTrs
↳5 InnermostUnusableRulesProof (BOTH BOUNDS(ID, ID), 0 ms)
↳6 CpxWeightedTrs
↳7 TypeInferenceProof (BOTH BOUNDS(ID, ID), 0 ms)
↳8 CpxTypedWeightedTrs
↳9 CompletionProof (UPPER BOUND(ID), 0 ms)
↳10 CpxTypedWeightedCompleteTrs
↳11 CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID), 0 ms)
↳12 CpxRNTS
↳13 CompleteCoflocoProof (⇔, 451 ms)
↳14 BOUNDS(1, n^2)
U11(tt, V2) → U12(isNat(activate(V2)))
U12(tt) → tt
U21(tt) → tt
U31(tt, N) → activate(N)
U41(tt, M, N) → U42(isNat(activate(N)), activate(M), activate(N))
U42(tt, M, N) → s(plus(activate(N), activate(M)))
isNat(n__0) → tt
isNat(n__plus(V1, V2)) → U11(isNat(activate(V1)), activate(V2))
isNat(n__s(V1)) → U21(isNat(activate(V1)))
plus(N, 0) → U31(isNat(N), N)
plus(N, s(M)) → U41(isNat(M), M, N)
0 → n__0
plus(X1, X2) → n__plus(X1, X2)
s(X) → n__s(X)
activate(n__0) → 0
activate(n__plus(X1, X2)) → plus(activate(X1), activate(X2))
activate(n__s(X)) → s(activate(X))
activate(X) → X
U11(tt, V2) → U12(isNat(activate(V2))) [1]
U12(tt) → tt [1]
U21(tt) → tt [1]
U31(tt, N) → activate(N) [1]
U41(tt, M, N) → U42(isNat(activate(N)), activate(M), activate(N)) [1]
U42(tt, M, N) → s(plus(activate(N), activate(M))) [1]
isNat(n__0) → tt [1]
isNat(n__plus(V1, V2)) → U11(isNat(activate(V1)), activate(V2)) [1]
isNat(n__s(V1)) → U21(isNat(activate(V1))) [1]
plus(N, 0) → U31(isNat(N), N) [1]
plus(N, s(M)) → U41(isNat(M), M, N) [1]
0 → n__0 [1]
plus(X1, X2) → n__plus(X1, X2) [1]
s(X) → n__s(X) [1]
activate(n__0) → 0 [1]
activate(n__plus(X1, X2)) → plus(activate(X1), activate(X2)) [1]
activate(n__s(X)) → s(activate(X)) [1]
activate(X) → X [1]
| 0 => 0' |
U11(tt, V2) → U12(isNat(activate(V2))) [1]
U12(tt) → tt [1]
U21(tt) → tt [1]
U31(tt, N) → activate(N) [1]
U41(tt, M, N) → U42(isNat(activate(N)), activate(M), activate(N)) [1]
U42(tt, M, N) → s(plus(activate(N), activate(M))) [1]
isNat(n__0) → tt [1]
isNat(n__plus(V1, V2)) → U11(isNat(activate(V1)), activate(V2)) [1]
isNat(n__s(V1)) → U21(isNat(activate(V1))) [1]
plus(N, 0') → U31(isNat(N), N) [1]
plus(N, s(M)) → U41(isNat(M), M, N) [1]
0' → n__0 [1]
plus(X1, X2) → n__plus(X1, X2) [1]
s(X) → n__s(X) [1]
activate(n__0) → 0' [1]
activate(n__plus(X1, X2)) → plus(activate(X1), activate(X2)) [1]
activate(n__s(X)) → s(activate(X)) [1]
activate(X) → X [1]
plus(N, 0') → U31(isNat(N), N) [1]
plus(N, s(M)) → U41(isNat(M), M, N) [1]
0' → n__0 [1]
s(X) → n__s(X) [1]
U11(tt, V2) → U12(isNat(activate(V2))) [1]
U12(tt) → tt [1]
U21(tt) → tt [1]
U31(tt, N) → activate(N) [1]
U41(tt, M, N) → U42(isNat(activate(N)), activate(M), activate(N)) [1]
U42(tt, M, N) → s(plus(activate(N), activate(M))) [1]
isNat(n__0) → tt [1]
isNat(n__plus(V1, V2)) → U11(isNat(activate(V1)), activate(V2)) [1]
isNat(n__s(V1)) → U21(isNat(activate(V1))) [1]
0' → n__0 [1]
plus(X1, X2) → n__plus(X1, X2) [1]
s(X) → n__s(X) [1]
activate(n__0) → 0' [1]
activate(n__plus(X1, X2)) → plus(activate(X1), activate(X2)) [1]
activate(n__s(X)) → s(activate(X)) [1]
activate(X) → X [1]
U11(tt, V2) → U12(isNat(activate(V2))) [1]
U12(tt) → tt [1]
U21(tt) → tt [1]
U31(tt, N) → activate(N) [1]
U41(tt, M, N) → U42(isNat(activate(N)), activate(M), activate(N)) [1]
U42(tt, M, N) → s(plus(activate(N), activate(M))) [1]
isNat(n__0) → tt [1]
isNat(n__plus(V1, V2)) → U11(isNat(activate(V1)), activate(V2)) [1]
isNat(n__s(V1)) → U21(isNat(activate(V1))) [1]
0' → n__0 [1]
plus(X1, X2) → n__plus(X1, X2) [1]
s(X) → n__s(X) [1]
activate(n__0) → 0' [1]
activate(n__plus(X1, X2)) → plus(activate(X1), activate(X2)) [1]
activate(n__s(X)) → s(activate(X)) [1]
activate(X) → X [1]
| U11 :: tt → n__0:n__plus:n__s → tt tt :: tt U12 :: tt → tt isNat :: n__0:n__plus:n__s → tt activate :: n__0:n__plus:n__s → n__0:n__plus:n__s U21 :: tt → tt U31 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s U41 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s U42 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s s :: n__0:n__plus:n__s → n__0:n__plus:n__s plus :: n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s n__0 :: n__0:n__plus:n__s n__plus :: n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s n__s :: n__0:n__plus:n__s → n__0:n__plus:n__s 0' :: n__0:n__plus:n__s |
| Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules:
The TRS has the following type information:
Rewrite Strategy: INNERMOST |
tt => 0
n__0 => 0
0' -{ 1 }→ 0 :|:
U11(z, z') -{ 1 }→ U12(isNat(activate(V2))) :|: z' = V2, V2 >= 0, z = 0
U12(z) -{ 1 }→ 0 :|: z = 0
U21(z) -{ 1 }→ 0 :|: z = 0
U31(z, z') -{ 1 }→ activate(N) :|: z' = N, z = 0, N >= 0
U41(z, z', z'') -{ 1 }→ U42(isNat(activate(N)), activate(M), activate(N)) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0
U42(z, z', z'') -{ 1 }→ s(plus(activate(N), activate(M))) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0
activate(z) -{ 1 }→ X :|: X >= 0, z = X
activate(z) -{ 1 }→ s(activate(X)) :|: z = 1 + X, X >= 0
activate(z) -{ 1 }→ plus(activate(X1), activate(X2)) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
activate(z) -{ 1 }→ 0' :|: z = 0
isNat(z) -{ 1 }→ U21(isNat(activate(V1))) :|: z = 1 + V1, V1 >= 0
isNat(z) -{ 1 }→ U11(isNat(activate(V1)), activate(V2)) :|: V1 >= 0, V2 >= 0, z = 1 + V1 + V2
isNat(z) -{ 1 }→ 0 :|: z = 0
plus(z, z') -{ 1 }→ 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
s(z) -{ 1 }→ 1 + X :|: X >= 0, z = X
| eq(start(V, V3, V4),0,[fun(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[fun1(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[fun2(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[fun3(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[fun4(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[fun5(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[isNat(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[fun6(Out)],[]). eq(start(V, V3, V4),0,[plus(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[s(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[activate(V, Out)],[V >= 0]). eq(fun(V, V3, Out),1,[activate(V21, Ret00),isNat(Ret00, Ret0),fun1(Ret0, Ret)],[Out = Ret,V3 = V21,V21 >= 0,V = 0]). eq(fun1(V, Out),1,[],[Out = 0,V = 0]). eq(fun2(V, Out),1,[],[Out = 0,V = 0]). eq(fun3(V, V3, Out),1,[activate(N1, Ret1)],[Out = Ret1,V3 = N1,V = 0,N1 >= 0]). eq(fun4(V, V3, V4, Out),1,[activate(N2, Ret001),isNat(Ret001, Ret01),activate(M1, Ret11),activate(N2, Ret2),fun5(Ret01, Ret11, Ret2, Ret3)],[Out = Ret3,V3 = M1,V = 0,V4 = N2,M1 >= 0,N2 >= 0]). eq(fun5(V, V3, V4, Out),1,[activate(N3, Ret002),activate(M2, Ret011),plus(Ret002, Ret011, Ret02),s(Ret02, Ret4)],[Out = Ret4,V3 = M2,V = 0,V4 = N3,M2 >= 0,N3 >= 0]). eq(isNat(V, Out),1,[],[Out = 0,V = 0]). eq(isNat(V, Out),1,[activate(V11, Ret003),isNat(Ret003, Ret03),activate(V22, Ret12),fun(Ret03, Ret12, Ret5)],[Out = Ret5,V11 >= 0,V22 >= 0,V = 1 + V11 + V22]). eq(isNat(V, Out),1,[activate(V12, Ret004),isNat(Ret004, Ret04),fun2(Ret04, Ret6)],[Out = Ret6,V = 1 + V12,V12 >= 0]). eq(fun6(Out),1,[],[Out = 0]). eq(plus(V, V3, Out),1,[],[Out = 1 + X11 + X21,X11 >= 0,X21 >= 0,V = X11,V3 = X21]). eq(s(V, Out),1,[],[Out = 1 + X3,X3 >= 0,V = X3]). eq(activate(V, Out),1,[fun6(Ret7)],[Out = Ret7,V = 0]). eq(activate(V, Out),1,[activate(X12, Ret05),activate(X22, Ret13),plus(Ret05, Ret13, Ret8)],[Out = Ret8,X12 >= 0,X22 >= 0,V = 1 + X12 + X22]). eq(activate(V, Out),1,[activate(X4, Ret06),s(Ret06, Ret9)],[Out = Ret9,V = 1 + X4,X4 >= 0]). eq(activate(V, Out),1,[],[Out = X5,X5 >= 0,V = X5]). input_output_vars(fun(V,V3,Out),[V,V3],[Out]). input_output_vars(fun1(V,Out),[V],[Out]). input_output_vars(fun2(V,Out),[V],[Out]). input_output_vars(fun3(V,V3,Out),[V,V3],[Out]). input_output_vars(fun4(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(fun5(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(isNat(V,Out),[V],[Out]). input_output_vars(fun6(Out),[],[Out]). input_output_vars(plus(V,V3,Out),[V,V3],[Out]). input_output_vars(s(V,Out),[V],[Out]). input_output_vars(activate(V,Out),[V],[Out]). |
CoFloCo proof output:
Preprocessing Cost Relations
=====================================
#### Computed strongly connected components
0. non_recursive : [fun6/1]
1. non_recursive : [plus/3]
2. non_recursive : [s/2]
3. recursive [non_tail,multiple] : [activate/2]
4. non_recursive : [fun1/2]
5. non_recursive : [fun2/2]
6. recursive [non_tail,multiple] : [fun/3,isNat/2]
7. non_recursive : [fun3/3]
8. non_recursive : [fun5/4]
9. non_recursive : [fun4/4]
10. non_recursive : [start/3]
#### Obtained direct recursion through partial evaluation
0. SCC is completely evaluated into other SCCs
1. SCC is completely evaluated into other SCCs
2. SCC is completely evaluated into other SCCs
3. SCC is partially evaluated into activate/2
4. SCC is completely evaluated into other SCCs
5. SCC is completely evaluated into other SCCs
6. SCC is partially evaluated into isNat/2
7. SCC is completely evaluated into other SCCs
8. SCC is partially evaluated into fun5/4
9. SCC is partially evaluated into fun4/4
10. SCC is partially evaluated into start/3
Control-Flow Refinement of Cost Relations
=====================================
### Specialization of cost equations activate/2
* CE 9 is refined into CE [18]
* CE 12 is refined into CE [19]
* CE 11 is refined into CE [20]
* CE 10 is refined into CE [21]
### Cost equations --> "Loop" of activate/2
* CEs [21] --> Loop 10
* CEs [20] --> Loop 11
* CEs [18,19] --> Loop 12
### Ranking functions of CR activate(V,Out)
* RF of phase [10,11]: [V]
#### Partial ranking functions of CR activate(V,Out)
* Partial RF of phase [10,11]:
- RF of loop [10:1,10:2,11:1]:
V
### Specialization of cost equations isNat/2
* CE 15 is refined into CE [22]
* CE 14 is refined into CE [23]
* CE 13 is refined into CE [24]
### Cost equations --> "Loop" of isNat/2
* CEs [24] --> Loop 13
* CEs [23] --> Loop 14
* CEs [22] --> Loop 15
### Ranking functions of CR isNat(V,Out)
* RF of phase [13,15]: [V]
#### Partial ranking functions of CR isNat(V,Out)
* Partial RF of phase [13,15]:
- RF of loop [13:1,13:2,15:1]:
V
### Specialization of cost equations fun5/4
* CE 17 is refined into CE [25]
### Cost equations --> "Loop" of fun5/4
* CEs [25] --> Loop 16
### Ranking functions of CR fun5(V,V3,V4,Out)
#### Partial ranking functions of CR fun5(V,V3,V4,Out)
### Specialization of cost equations fun4/4
* CE 16 is refined into CE [26,27]
### Cost equations --> "Loop" of fun4/4
* CEs [27] --> Loop 17
* CEs [26] --> Loop 18
### Ranking functions of CR fun4(V,V3,V4,Out)
#### Partial ranking functions of CR fun4(V,V3,V4,Out)
### Specialization of cost equations start/3
* CE 2 is refined into CE [28,29]
* CE 3 is refined into CE [30]
* CE 4 is refined into CE [31]
* CE 5 is refined into CE [32,33]
* CE 6 is refined into CE [34]
* CE 7 is refined into CE [35,36]
* CE 8 is refined into CE [37]
### Cost equations --> "Loop" of start/3
* CEs [28,29,30,31,32,33,34,35,36,37] --> Loop 19
### Ranking functions of CR start(V,V3,V4)
#### Partial ranking functions of CR start(V,V3,V4)
Computing Bounds
=====================================
#### Cost of chains of activate(V,Out):
* Chain [12]: 2
with precondition: [V=Out,V>=0]
* Chain [multiple([10,11],[[12]])]: 4*it(10)+2*it([12])+0
Such that:it([12]) =< V+1
aux(1) =< V
it(10) =< aux(1)
with precondition: [V=Out,V>=1]
#### Cost of chains of isNat(V,Out):
* Chain [14]: 1
with precondition: [V=0,Out=0]
* Chain [multiple([13,15],[[14]])]: 13*it(13)+1*it([14])+2*s(25)+4*s(26)+10*s(27)+8*s(28)+0
Such that:it([14]) =< V+1
aux(10) =< V
it(13) =< aux(10)
aux(6) =< aux(10)+1
aux(7) =< aux(10)
s(29) =< it(13)*aux(10)
s(31) =< it(13)*aux(6)
s(30) =< it(13)*aux(7)
s(25) =< it(13)*aux(6)
s(27) =< s(31)
s(28) =< s(30)
s(26) =< s(29)
with precondition: [Out=0,V>=1]
#### Cost of chains of fun5(V,V3,V4,Out):
* Chain [16]: 2*s(35)+4*s(36)+2*s(38)+4*s(39)+7
Such that:s(37) =< V3
s(38) =< V3+1
s(34) =< V4
s(35) =< V4+1
s(39) =< s(37)
s(36) =< s(34)
with precondition: [V=0,V3+V4+2=Out,V3>=0,V4>=0]
#### Cost of chains of fun4(V,V3,V4,Out):
* Chain [18]: 6*s(41)+4*s(44)+8*s(45)+15
Such that:aux(12) =< 1
aux(13) =< V3
aux(14) =< V3+1
s(41) =< aux(12)
s(44) =< aux(14)
s(45) =< aux(13)
with precondition: [V=0,V4=0,V3+2=Out,V3>=0]
* Chain [17]: 7*s(56)+25*s(57)+2*s(66)+10*s(67)+8*s(68)+4*s(69)+4*s(71)+8*s(72)+14
Such that:aux(15) =< V3
aux(16) =< V3+1
aux(17) =< V4
aux(18) =< V4+1
s(71) =< aux(16)
s(56) =< aux(18)
s(72) =< aux(15)
s(57) =< aux(17)
s(61) =< aux(17)+1
s(62) =< aux(17)
s(63) =< s(57)*aux(17)
s(64) =< s(57)*s(61)
s(65) =< s(57)*s(62)
s(66) =< s(57)*s(61)
s(67) =< s(64)
s(68) =< s(65)
s(69) =< s(63)
with precondition: [V=0,V3+V4+2=Out,V3>=0,V4>=1]
#### Cost of chains of start(V,V3,V4):
* Chain [19]: 8*s(83)+15*s(86)+41*s(87)+2*s(96)+10*s(97)+8*s(98)+4*s(99)+9*s(114)+29*s(116)+2*s(122)+10*s(123)+8*s(124)+4*s(125)+3*s(132)+17*s(134)+2*s(140)+10*s(141)+8*s(142)+4*s(143)+15
Such that:aux(21) =< 1
aux(22) =< V
aux(23) =< V+1
aux(24) =< V3
aux(25) =< V3+1
aux(26) =< V4
aux(27) =< V4+1
s(83) =< aux(21)
s(132) =< aux(23)
s(86) =< aux(25)
s(114) =< aux(27)
s(87) =< aux(24)
s(134) =< aux(22)
s(135) =< aux(22)+1
s(136) =< aux(22)
s(137) =< s(134)*aux(22)
s(138) =< s(134)*s(135)
s(139) =< s(134)*s(136)
s(140) =< s(134)*s(135)
s(141) =< s(138)
s(142) =< s(139)
s(143) =< s(137)
s(91) =< aux(24)+1
s(92) =< aux(24)
s(93) =< s(87)*aux(24)
s(94) =< s(87)*s(91)
s(95) =< s(87)*s(92)
s(96) =< s(87)*s(91)
s(97) =< s(94)
s(98) =< s(95)
s(99) =< s(93)
s(116) =< aux(26)
s(117) =< aux(26)+1
s(118) =< aux(26)
s(119) =< s(116)*aux(26)
s(120) =< s(116)*s(117)
s(121) =< s(116)*s(118)
s(122) =< s(116)*s(117)
s(123) =< s(120)
s(124) =< s(121)
s(125) =< s(119)
with precondition: []
Closed-form bounds of start(V,V3,V4):
-------------------------------------
* Chain [19] with precondition: []
- Upper bound: nat(V)*29+23+nat(V)*24*nat(V)+nat(V3)*53+nat(V3)*24*nat(V3)+nat(V4)*41+nat(V4)*24*nat(V4)+nat(V+1)*3+nat(V3+1)*15+nat(V4+1)*9
- Complexity: n^2
### Maximum cost of start(V,V3,V4): nat(V)*29+23+nat(V)*24*nat(V)+nat(V3)*53+nat(V3)*24*nat(V3)+nat(V4)*41+nat(V4)*24*nat(V4)+nat(V+1)*3+nat(V3+1)*15+nat(V4+1)*9
Asymptotic class: n^2
* Total analysis performed in 305 ms.